package heap

type SliceHeap struct {
	slice    []int // 数组实现的容器
	capacity int   // 容量
}

// sort 堆排序
func (receiver *SliceHeap) sort() {

	// 先堆化
	receiver.buildHeap()
	// 从 n 到 1 	逐一向后排列再堆化
	for end := len(receiver.slice) - 1; end > 1; {
		// 先将堆顶元素放到堆底部
		temp := receiver.slice[1]
		receiver.slice[1] = receiver.slice[end]
		receiver.slice[end] = temp
		// 剩下区间元素进行堆化
		end -= 1
		receiver.toHeapWithRange(1, end)
	}
}

// buildHeap 构造堆
func (receiver *SliceHeap) buildHeap() {

	for index := len(receiver.slice); index >= 1; index-- {
		receiver.toHeap(index)
	}
}

// deleteFirst 删除元素
func (receiver *SliceHeap) deleteFirst() {

	if len(receiver.slice) <= 1 {
		return
	}
	// 将最后一个叶子节点放置在根节点，然后从头节点开始堆化
	receiver.slice[1] = receiver.slice[len(receiver.slice)-1]
	receiver.slice[len(receiver.slice)-1] = 0
	receiver.toHeap(1)
}

// toHeapWithRange 堆化指定区间的元素
func (receiver *SliceHeap) toHeapWithRange(index, end int) {

	for {
		curr := index
		// 左节点判定
		if end >= 2*index && receiver.slice[2*index] > receiver.slice[index] {
			curr = 2 * index
		}
		// 右节点判定
		if end >= 2*index+1 && receiver.slice[2*index+1] > receiver.slice[2*index] {
			curr = 2*index + 1
		}
		// 已经找到合适的交换位置
		if index == curr {
			return
		}

		temp := receiver.slice[index]
		receiver.slice[index] = receiver.slice[curr]
		receiver.slice[curr] = temp
	}
}

// toHeapWithRange 堆化
func (receiver *SliceHeap) toHeap(index int) {

	for {
		curr := index
		// 左节点判定
		if len(receiver.slice) >= 2*index && receiver.slice[2*index] > receiver.slice[index] {
			curr = 2 * index
		}
		// 右节点判定
		if len(receiver.slice) >= 2*index+1 && receiver.slice[2*index+1] > receiver.slice[2*index] {
			curr = 2*index + 1
		}
		// 已经找到合适的交换位置
		if index == curr {
			return
		}

		temp := receiver.slice[index]
		receiver.slice[index] = receiver.slice[curr]
		receiver.slice[curr] = temp
	}

}

// deleteTop 删除堆顶元素
func (receiver *SliceHeap) deleteTop() {
	// 堆中无数据
	if len(receiver.slice) <= 1 {
		return
	}
	// 自上向下堆化，根节点被删除后，提拔下个节点到上级直到叶子节点，该叶子节点最后被置为空
	curr := 1
	for index := 1; len(receiver.slice) >= 2*index; index = 2 * index { // 遍历到叶子节点就退出
		curr = 2 * index
		if len(receiver.slice) >= 2*index+1 && receiver.slice[2*index] < receiver.slice[2*index+1] {
			curr = 2*index + 1
		}
		// 将 curr 上的数据替换至index
		receiver.slice[index] = receiver.slice[curr]
		index = curr
	}

	receiver.slice[curr] = 0

}

// insert 往堆中插入一个元素
func (receiver *SliceHeap) insert(element int) {

	receiver.slice = append(receiver.slice, element)
	// 开始堆化
	for index := len(receiver.slice) - 1; index > 1; {
		fatherIndex := index / 2
		if receiver.slice[index] <= receiver.slice[fatherIndex] {
			// 退出循环
			return
		}

		temp := receiver.slice[index]
		receiver.slice[index] = receiver.slice[fatherIndex]
		receiver.slice[fatherIndex] = temp
		index = fatherIndex
	}
}
